
# 树是否是镜像对称的。一般树的算法都会采用递归算法，关键是找到如何递归
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        return self.isMirror(root, root)

    def isMirror(self, leftChild, rightChild):
        if (not leftChild) and (not rightChild):    # 都为空
            return True
        if (not leftChild) or (not rightChild):
            return False
        if leftChild.val == rightChild.val:
            return self.isMirror(leftChild.left, rightChild.right) and self.isMirror(leftChild.right,rightChild.left)
        return False

'''
关于如何递归：重点是要想这个题目如何实现：
    1. 首先看根节点是不是为空，为空说明对称
    2. 根节点不为空看是否左右孩子是否为空。一个为空不对称，两个都为空对称，都有就要看对应数值是否相同
    3. 所以要考虑新建一个函数用来处理孩子对称问题。传入节点的左右孩子判断节点的左右孩子是否对称
        。 如果左右孩子都为空说明对称
        。 一个为空一个不为空则不对成
        。 都不为空但是数值相等接着需要左子树的左儿子和右子树的右儿子对称，左子树的右儿子和右子树的左儿子对称(实现了递归)
        。 数值不相等就是不对称。返回False
    这里面将根节点分身当作子树子和右子树传过去是没有问题的。整个过程重点熟悉一下就可以！
'''

'''
递归程序往往从上而下。直到达到最初条件。而迭代往往是从最简单的出发达到最终条件。所以往往需要列表或者数组来保存之前的值用来迭代。比如树。就需要利用一个列表
来保存遍历过程中的节点。往往递归特别吃内存但是代码优雅甚至便于实现。但是迭代则可能内存占用会相对较少？
'''
import collections
# 迭代搞二叉树时一定是需要一个列表用来存储中间东西的.其核心原理在于一对一对的进去和一对一对的出来。一样的话成对这样最后也就为空了，不一样的话部位空或者直接False了。
def isSymmetric(self, root: TreeNode) -> bool:
    # 迭代法求结果
    if not root: return True  # 根节点为空，不为空就添加左右子树
    queue = collections.deque([root.left, root.right])

    while queue:
        node1 = queue.popleft()
        node2 = queue.popleft()  # 弹出两个节点
        # 如果都为空那就不能再加入列表了。有一个为空说明不对称。都不为空比较数字
        if (not node1) and (not node2):
            continue
        if (node1 == None or node2 == None) or (node1.val != node2.val):
            return False
        left1, right1 = node1.left, node1.right
        left2, right2 = node2.left, node2.right
        queue.append(left1)
        queue.append(right2)
        queue.append(right1)
        queue.append(left2)
    return True